package swardToOffer.struct_5_stack_or_queue;
// 面试题31：栈的压入、弹出序列
// 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是
// 否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、
// 5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但
// 4、3、5、1、2就不可能是该压栈序列的弹出序列。

import java.util.Stack;

/**
 * 考虑借用一个辅助栈 stack  ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
 * 入栈操作： 按照压栈序列的顺序执行。
 * 出栈操作： 每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立，
 * 将符合弹出序列顺序的栈顶元素全部弹出。
 */
public class StackPushPopOrder {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length || pushed.length == 0) return false;
        Stack<Integer> stack = new Stack<>();
        int k = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek().equals(popped[k])) {
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }

    //由于题目中假设压入栈的所有数字均不相等，所以可以通过下标变化模拟压栈出栈的过程
    //此时的空间复杂度就为O(1)了
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        if (pushed.length != popped.length || pushed.length == 0) return false;
        int i = 0, j = 0;
        for (int e : pushed) {
            pushed[i] = e; //模拟压栈
            while (i >= 0 && pushed[i] == popped[j]) { //模拟出栈
                j++;
                i--;
            }
            i++;
        }
        return i == 0;

    }

    public static void main(String[] args) {
        StackPushPopOrder Main = new StackPushPopOrder();
        int[] pushed = {1, 2, 3, 4, 5};
        int[] popped = {4, 5, 3, 2, 1};
//        int[] popped = {4, 3, 5, 1, 2};
        System.out.println(Main.validateStackSequences2(pushed, popped));
    }
}
